/*
 * @lc app=leetcode.cn id=931 lang=cpp
 *
 * [931] 下降路径最小和
 *
 * https://leetcode.cn/problems/minimum-falling-path-sum/description/
 *
 * algorithms
 * Medium (67.54%)
 * Likes:    346
 * Dislikes: 0
 * Total Accepted:    106.3K
 * Total Submissions: 157.4K
 * Testcase Example:  '[[2,1,3],[6,5,4],[7,8,9]]'
 *
 * 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
 *
 * 下降路径
 * 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置
 * (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1)
 * 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 *
 * 输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
 * 输出：13
 * 解释：如图所示，为和最小的两条下降路径
 *
 *
 * 示例 2：
 *
 *
 *
 *
 * 输入：matrix = [[-19,57],[-40,-5]]
 * 输出：-59
 * 解释：如图所示，为和最小的下降路径
 *
 *
 *
 *
 * 提示：
 *
 *
 * n == matrix.length == matrix[i].length
 * 1 <= n <= 100
 * -100 <= matrix[i][j] <= 100
 *
 *
 */
#include <bits/stdc++.h>

#include "help_struct.h"
using namespace std;
// @lc code=start
class Solution {
public:
    // int minFallingPathSum(vector<vector<int>>& matrix) {
    //     int n = matrix.size();
    //     vector<vector<int>> dp(n - 1, vector<int>(n, 0));
    //     dp.insert(dp.begin(), matrix[0]);
    //     for (int i = 1; i < n; i++) {
    //         for (int j = 0; j < n; j++) {
    //             dp[i][j] = dp[i - 1][j] + matrix[i][j];
    //             if (j > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
    //             if (j < n - 1) dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + matrix[i][j]);
    //         }
    //     }
    //     return *min_element(dp[n - 1].begin(), dp[n - 1].end());
    // }

    // 滚动数组优化空间
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp = {matrix[0], vector<int>(n, 0)};

        for (int i = 1; i < n; i++) {
            int cur = i & 1, pre = (i - 1) & 1;
            for (int j = 0; j < n; j++) {
                dp[cur][j] = dp[pre][j] + matrix[i][j];
                if (j > 0) dp[cur][j] = min(dp[cur][j], dp[pre][j - 1] + matrix[i][j]);
                if (j < n - 1) dp[cur][j] = min(dp[cur][j], dp[pre][j + 1] + matrix[i][j]);
            }
        }
        return *min_element(dp[(n - 1) & 1].begin(), dp[(n - 1) & 1].end());
    }
};
// @lc code=end
